Spin off question

Is it possible to hack a SIM card to add a javacard application on it (to properly format international numbers)? If yes, how?

Original Question

1. In my previous phone carrier I could just dial +55 11 99883655 and it would just work.

2. Now I moved to a new carrier and it doesn't work anymore! When I dial the same international number it keeps saying the number isn't formated correctly.

How can I get my iPhone to understand international numbering back again?

I've got over 100 contacts with numbers stored in this format already, and I want to keep them that way.

^{edit: I originally asked this question here, moved it to apple stackexchange and now I'm bringing a new one (hopefuly).}